/**
 * 861. 翻转矩阵后的得分
 * https://leetcode-cn.com/problems/score-after-flipping-matrix/
 */
public class Solutions_861 {
    public static void main(String[] args) {
//        int[][] matrix = {{0, 0, 1, 1},
//                          {1, 0, 1, 0},
//                          {1, 1, 0, 0}};  // output: 39
        // 转换为 {{1, 1, 1, 1}, {1, 0, 0, 1}, {1, 1, 1, 1}}
        // 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

        int[][] matrix = {{0, 1},
                          {0, 1},
                          {0, 1},
                          {0, 0}};  // output: 11
        // 转换为 {{1, 1}, {1, 1}, {1, 1}, {1, 0}}  3 + 3 + 3 + 2 = 11

//        int[][] matrix = {{0}};  // output: 1
        // 转换为 {{1}}

        int result = matrixScore(matrix);
        System.out.println(result);
    }

    /**
     * 解题思路：（贪心思想）
     * 1. 将每 1 行的第 1 列都转换成 1（二进制中，第 1 位是 1 时，永远比后面的位的总和都大，即 1000 > 0111）
     * 2. 后面的每一列，根据 1 的个数来变化
     *      2.1 若是 1 的数量小于 0 的数量，那么该列需要变化
     */
    public static int matrixScore(int[][] A) {
        int row = A.length, col = A[0].length;
        for (int i = 0; i < row; i++) {
            if (A[i][0] == 0) {
                // 如果第 1 位是 0，那么该行转化
                rowTrans(A, i);
            }
        }
        // 从第 1 列开始，根据 0 和 1 的个数，判断是否需要进行列转化
        for (int j = 1; j < col; j++) {
            int one = 0;
            for (int i = 0; i < row; i++) {
                one += A[i][j] == 1 ? 1 : 0;
            }
            if (one < ((row + 1) / 2)) {
                // 1 列中，1 的个数小于 0 的个数时，该列转化
                colTrans(A, j);
            }
        }
        int res = 0;
        for (int[] arr : A) {
            int cur = 0;
            // 计算每一行表示的二进制的值
            for (int i = 0; i < col; i++) {
                cur = (cur << 1) + arr[i];
            }
            res += cur;
        }
        return res;
    }

    /**
     * matrix 中的 row 行转化，0 变成 1，1 变成 0
     */
    public static void rowTrans(int[][] matrix, int row) {
        for (int i = 0; i < matrix[row].length; i++) {
            matrix[row][i] ^= 1;
        }
    }

    /**
     * matrix 中的 col 列转化，0 变成 1，1 变成 0
     */
    public static void colTrans(int[][] matrix, int col) {
        for (int[] arr : matrix) {
            arr[col] ^= 1;
        }
    }
}
